What is Linear Search 什麼是線性搜尋

從 input dataset 最前端開始，遍歷每個值一直到找到目標值，如果沒有找到目標值的話，便逐個搜尋直到資料結束

Steps of Linear Search

圖片來源

1. Start 從index 0 開始
   Begin at the first element in the collection.
2. Compare 比較
   Check if the current element matches the desired value.
3. Found 找到與目標符合的元素
   If a match is found, return true or the index of the current element.
4. Move 移動到下個元素
   If not, move to the next element by incrementing the index by 1.
5. Repeat 2-4 重複2-4
   Repeat steps 2-4 until the end of the collection is reached.
6. Not Found 未找到
   If the element is not found by the end, return a failure message(e.g., false or -1)

Complexity of Linear Search

• Best Case: O(1)
  在開頭就找到目標值
• Average Case: O(n)
• Worst Case: O(n)
  遍歷整個資料集都沒找到

Implementation of Linear Search (find specific value in array)

let dataSet = [5,1,7,14,3,56,12,76,55];

function linearSearch(dataSet , desired){
    for(let current=0;current<dataSet.length;current++){
        if (dataSet[current] === desired){
            return current;
        }
    }
    return -1;
}

linearSearch( dataSet, 76); // 7
linearSearch( dataSet, 89); // -1

Extra coding exercise:Facing The Sun

Given an array height representing the heights of buildings. You have to count the buildings that will see the sunrise (Assume the sun rises on the side of the array starting point).
Note: The height of the building should be strictly greater than the height of the buildings left in order to see the sun.

給予一個包含所有建築物的 array，寫出 function 來算出多少棟建築物可被陽光照到

提示：能被陽光照到的條件為，該建築物的高度必須要高於任何位於其左邊的建築物

Answer:

const heightOfTheBuildings = [];

function countBuildings(heights){
    let buildingsCanSeeSun = 1; // the leftest building can get the sunshine
    let highestBuilding = heights[0];
    for(let i=0;i<heights.length;i++){
        if(heights[i]> highestBuilding){
            buildingsCanSeeSun++;
            highestBuilding = heights[i];
        }
    }
    return buildingsCanSeeSun;
}

相關資源

Linear Search Algorithm
https://www.tutorialspoint.com/data_structures_algorithms/linear_search_algorithm.htm
Introduction to Linear Search Algorithm
https://www.geeksforgeeks.org/linear-search/
Linear Search Time Complexity
https://www.w3schools.com/dsa/dsa_timecomplexity_linearsearch.php